package dataTypeTests;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class ArrayListTester<T extends Comparable<? super T>> implements DataTypeTester<T> {
	ArrayList<T> array;
	
	ArrayListTester(List<T> list) {
		array = new ArrayList<T>(list);
	}
	
	@Override
	public long measureBinSearch(int iterations) {
		long avgTime = 0;
		Collections.sort(array);
		for (int i = 0; i < iterations; i++) {
			Random random = new Random();
			int index = random.nextInt(array.size()-1);
			T elem = array.get(index);
			long estTime = System.nanoTime();
			binSearch(elem, 0, array.size()-1);
			estTime = System.nanoTime() - estTime;
			avgTime += estTime;
		}
		avgTime /= iterations;
		return avgTime;
	}
	
	private int binSearch(T elem, int l, int r) {
		if (r == l) {
			int compare = array.get(l).compareTo(elem);
			if (compare == 0) return l;
			else return -1;
		}
		int pivotIndex = (l+r)/2;
		T pivot = array.get(pivotIndex);
		int compare = pivot.compareTo(elem);
		if (compare == 0) {
			return pivotIndex;
		} else {
			if (compare < 0) return binSearch(elem, pivotIndex+1, r);
			else return binSearch(elem, l, pivotIndex-1);
		}
	}

	@Override
	public long measureBubbleSort(int iterations) {
		// TODO Auto-generated method stub
		return 0;
	}

}
